package _18_剑指OfferII;

public class _116_剑指OfferII省份数量 {

    public static void main(String[] args) {


        _116_剑指OfferII省份数量 v = new _116_剑指OfferII省份数量();

        int[][] is = {{1,0,0},{0,1,0},{0,0,1}};

        System.out.println(v.findCircleNum(is));
    }

    // 深度搜索
    public int findCircleNum(int[][] isConnected) {
        int total = 0;
        int province = isConnected.length;
        boolean[] visited = new boolean[province];
        for (int i = 0; i < province; ++i) {
            // 当前省份没有被访问过
            if (!visited[i]) {
                dfs(isConnected, i, visited);
                total++;
            }
        }
        return total;
    }

    private void dfs(int[][] isConnected, int index, boolean[] visited) {
        visited[index] = true;
        int[] cur = isConnected[index];
        for (int i = 0; i < cur.length; ++i) {
            if (!visited[i] && cur[i] == 1) dfs(isConnected, i, visited);
        }
    }

}
